UVa/705 - Slash maze/705.3.cpp

   1 #include <algorithm>
   2 #include <iostream>
   3 #include <map>
   4 #include <vector>
   5 #include <set>
   6
   7 using namespace std;
   8
   9 typedef pair<int, int> node;
  10 typedef map<node, set<node> > graph;
  11
  12 int longest;
  13 int qty;
  14
  15 graph g;
  16
  17 char m[75][75];
  18
  19 map<node, int> d;
  20
  21 void dfs(const node &u){
  22   set<node> &vecinos = g[u];
  23   for (set<node>::iterator i = vecinos.begin(); i != vecinos.end(); ++i){
  24     if (d.count(*i)){
  25       if (d[*i] + 1 < d[u]){
  26         //printf("Cycle from (%d, %d) to (%d, %d)\n", i->first, i->second, u.first, u.second);
  27         qty++;
  28         longest = max(longest, d[u] - d[*i] + 1);
  29       }
  30     }else{
  31       d[*i] = d[u] + 1;
  32       dfs(*i);
  33     }
  34   }
  35 }
  36
  37 void connect(const node &u, const node &v){
  38   g[u].insert(v);
  39   g[v].insert(u);
  40 }
  41
  42 int main(){
  43   int w,h;
  44   int mazeNo = 1;
  45   while (cin >> w >> h && w && h){
  46     g.clear();
  47     d.clear();
  48
  49     longest = -1;
  50     qty = 0;
  51
  52     for (int i=0; i<w; ++i){
  53       for (int j=0; j<h; ++j){
  54         cin >> m[i][j];
  55       }
  56     }
  57
  58     for (int i=0; i<w; ++i){
  59       for (int j=0; j<h; ++j){
  60
  61         //laterales
  62         connect(node(i, 2*j), node(i, 2*j-1));
  63         connect(node(i, 2*j+1), node(i, 2*j+2));
  64
  65
  66         char c = m[i][j];
  67         if (c == '\\'){
  68           int ni, nj;
  69
  70           //arriba
  71           ni = i-1;
  72           nj = j;
  73           if (0 <= ni && ni < w && 0 <= nj && nj < h &&
  74               m[ni][nj] != m[i][j]){
  75
  76             connect(node(i, 2*j+1), node(ni, 2*nj+1));
  77           }
  78
  79           //abajo
  80           ni = i+1;
  81           nj = j;
  82           if (0 <= ni && ni < w && 0 <= nj && nj < h &&
  83               m[ni][nj] != m[i][j]){
  84
  85             connect(node(i, 2*j), node(ni, 2*nj));
  86           }
  87
  88         }else if (c == '/'){
  89           int ni, nj;
  90
  91           //arriba
  92           ni = i-1;
  93           nj = j;
  94           if (0 <= ni && ni < w && 0 <= nj && nj < h &&
  95               m[ni][nj] != m[i][j]){
  96             connect(node(i, 2*j), node(ni, 2*nj));
  97           }
  98
  99           //abajo
 100           ni = i+1;
 101           nj = j;
 102           if (0 <= ni && ni < w && 0 <= nj && nj < h &&
 103               m[ni][nj] != m[i][j]){
 104             connect(node(i, 2*j+1), node(ni, 2*nj+1));
 105           }
 106
 107
 108         }else{
 109           cerr << "Unrecognized char in input" << endl;
 110         }
 111       }
 112     }
 113
 114     /*for (map<node, set<node> >::iterator i = g.begin(); i != g.end(); ++i){
 115       printf("Vecinos de (%d, %d):\n", i->first.first, i->first.second);
 116       set<node> v = i->second;
 117       for (set<node>::iterator j = v.begin(); j != v.end(); ++j){
 118         printf("(%d, %d) ", j->first, j->second);
 119       }
 120       cout << endl;
 121       }*/
 122
 123     for (map<node, set<node> >::iterator i = g.begin(); i != g.end(); ++i){
 124       if (d.count(i->first) == 0){
 125         d[i->first] = 0;
 126         dfs(i->first);
 127       }
 128     }
 129
 130     printf("Maze #%d:\n", mazeNo++);
 131     if (qty == 0){
 132       printf("There are no cycles.\n");
 133     }else{
 134       printf("%d Cycles; the longest has length %d\n", qty, longest);
 135     }
 136     printf("\n");
 137
 138
 139
 140   }
 141   return 0;
 142 }
 143